package bill.study.algorithms.linkedlist;

import java.util.ArrayList;
import java.util.List;


public class Reverse {
	
	/***
	 * Returning a node is essential. Although they claims that Java always
	 * passes by reference. We have to understand the reference is copied. (it
	 * is a fresh pointer), and we are only moving the copied the pointer
	 * around. Unless we keep the head intact and copying the values in the
	 * list, we have to return a new head!!!
	 * 
	 * @param head
	 * @return
	 */
	private static Node reverse(Node head) {
		if (head == null || head.next == null) {
			return head;
		}
		Node pre = null;
		while (head != null) {
			Node tmp = head.next;
			head.next = pre;
			pre = head;
			head = tmp;
		}
		System.out.println("done");
		return pre;
	}
	
	public static void main(String[] args) {
		/**
		 * 1. Test reverse in pairs
		 */

		Node head = new Node(1, new Node(2, new Node(3, new Node(4, null))));
		

		/***
		 * test reverse
		 */
		System.out.println("-----------------test reverse-----------------");
		head = new Node(1, new Node(2, new Node(3, new Node(4, null))));
		System.out.println(head);
		Node newhead = reverse(head);
		System.out.println(newhead);

		head = null;
		System.out.println(head);
		newhead = reverse(head);
		System.out.println(newhead);

		head = new Node(1, new Node(2, new Node(3, null)));
		System.out.println(head);
		newhead = reverse(head);
		System.out.println(newhead);

		head = new Node(1, null);
		System.out.println(head);
		newhead = reverse(head);
		System.out.println(newhead);

		/**
		 * testing pass by reference
		 */
		System.out
				.println("Although they claims that Java always 	 passes by reference. We have to understand the reference is copied. (it is a fresh pointer)");
		List<Integer> l = new ArrayList<Integer>();
		l.add(2);
		System.out.println(l);
		System.out.println(l);

	}

	public static void removeList() {

	}

	private static class Node {
		int val;
		Node next;

		public Node(int v, Node n) {
			this.val = v;
			this.next = n;
		}

		public String toString() {
			StringBuilder sb = new StringBuilder();
			Node runner = this;
			while (runner != null) {
				sb.append(runner.val + " ");
				runner = runner.next;
			}
			return sb.toString();
		}
	}

}
